﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

class Solution
{
public:
	int integerReplacement(int n)
	{
		int ret = 0;
		while (n > 1)
		{
			// 分类讨论
			if (n % 2 == 0)
			{
				ret++;
				n /= 2;
			}
			else
			{
				if (n == 3)
				{
					ret += 2;
					n = 1;
				}
				else if (n % 4 == 1)
				{
					ret += 2;
					n /= 2;
				}
				else
				{
					ret += 2;
					n = n / 2 + 1;
				}
			}
		}
		return ret;
	}
};

int main()
{
	int n = 8;

	cout << Solution().integerReplacement(n) << endl;

	return 0;
}
